package cn.bellychang.linkedlist.liuxin;

import cn.bellychang.iiterface.liuxin.Iterator;
import cn.bellychang.iiterface.liuxin.List;

import java.util.Optional;

/**
 * one-way linked list
 *
 * @author: bellychang
 * @date: 2020/2/6
 */
public class LinkedList<E> implements List<E> {

    private Node<E> head;

    private Node<E> tail;

    private int size;

    public LinkedList() {
        head = new Node<>(null);
        tail = new Node<>(null);
    }

    /**
     * add to the tail
     *
     * @param e
     */
    @Override
    public void addLast(E e) {
        // check if tail is null node
        if (head.value==null) {
            head.value = e;
        } else if (tail.value==null) {
            tail.value = e;
            // test case: addFirst addFirst and then addLast
            Node<E> lessNode = find(size - 1);
            lessNode.next = tail;
        } else {
            Node<E> newNode = new Node<>(e);
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    @Override
    public String toString() {
        Node<E> temp = head;
        StringBuilder builder = new StringBuilder();
        while (temp != null && temp.value != null) {
            builder.append(temp.value)
                    .append("->");
            temp = temp.next;
        }
        return builder.length() >= 2 ? builder.toString().substring(0, builder.length() - 2) : builder.toString();
    }

    /**
     * index  [0,getSize-1]
     * @param index
     * @param e
     */
    @Override
    public void add(int index, E e) {
        rangeAddCheck(index);
        Node<E> newNode = new Node<>(e);
        // newNode -> head
        if (index==0) {
            if (head.value == null) {
                head.value = e;
            } else {
                newNode.next = head;
                head = newNode;
            }
        } else if (index == size) {
            // tail -> newNode
            if (tail.value == null) {
                tail.value = e;
                head.next = tail;
            } else {
                tail.next = newNode;
                tail = newNode;
            }
        } else {
            // temp -> newNode -> temp.next
            Node<E> lessNode = find(index);
            newNode.next = lessNode.next;
            lessNode.next = newNode;
        }
        size++;
    }

    private Node<E> find(int index) {
        Node<E> temp = head;
        for (int i = 0; i < index; i++) {
               temp = temp.next;
        }
        return temp;
    }

    private void rangeAddCheck(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
    }

    private void rangeGetCheck(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public E get(int index) {
        rangeGetCheck(index);
        return find(index).value;
    }

    @Override
    public E remove(int index) {
        rangeGetCheck(index);
        Node<E> node = find(index);
        // remove head
        if (index == 0) {
            head = node.next;
        } else if (index == (size - 1)) {
            tail = find(index - 1);
            tail.next = null;
        } else {
            find(index - 1).next = find(index+1);
        }
        size--;
        return node.value;
    }

    @Override
    public int getSize() {
        return size;
    }

    private static class Node<E> {
        private E value;
        private Node<E> next;

        public Node(E value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return Optional.ofNullable(value).orElse((E) "null").toString();
        }
    }

    public Iterator<E> iterator() {
        return new LinkedListIterator<>();
    }

    private class LinkedListIterator<E> implements Iterator<E>{

        int position = 0;

        @Override
        public boolean hasNext() {
            return position <= (size - 1);
        }

        @Override
        public E next() {
            return (E) get(position++);
        }
    }
}
